{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Card Flipping Game"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: flipgame"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #翻转卡片游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在桌子上有 <code>n</code> 张卡片，每张卡片的正面和背面都写着一个正数（正面与背面上的数有可能不一样）。</p>\n",
    "\n",
    "<p>我们可以先翻转任意张卡片，然后选择其中一张卡片。</p>\n",
    "\n",
    "<p>如果选中的那张卡片背面的数字 <code>x</code> 与任意一张卡片的正面的数字都不同，那么这个数字是我们想要的数字。</p>\n",
    "\n",
    "<p>哪个数是这些想要的数字中最小的数（找到这些数中的最小值）呢？如果没有一个数字符合要求的，输出 <code>0</code> 。</p>\n",
    "\n",
    "<p>其中, <code>fronts[i]</code>&nbsp;和&nbsp;<code>backs[i]</code>&nbsp;分别代表第&nbsp;<code>i</code>&nbsp;张卡片的正面和背面的数字。</p>\n",
    "\n",
    "<p>如果我们通过翻转卡片来交换正面与背面上的数，那么当初在正面的数就变成背面的数，背面的数就变成正面的数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>fronts = [1,2,4,4,7], backs = [1,3,4,1,3]\n",
    "<strong>输出：</strong><code>2</code>\n",
    "<strong>解释：</strong>假设我们翻转第二张卡片，那么在正面的数变成了 <code>[1,3,4,4,7]</code> ， 背面的数变成了 <code>[1,2,4,1,3]。</code>\n",
    "接着我们选择第二张卡片，因为现在该卡片的背面的数是 2，2 与任意卡片上正面的数都不同，所以 2 就是我们想要的数字。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>fronts = [1], backs = [1]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>\n",
    "无论如何翻转都无法得到想要的数字，所以返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == fronts.length == backs.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= fronts[i], backs[i] &lt;= 2000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [card-flipping-game](https://leetcode.cn/problems/card-flipping-game/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [card-flipping-game](https://leetcode.cn/problems/card-flipping-game/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,4,4,7]\\n[1,3,4,1,3]', '[1]\\n[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        same = {fronts[i] for i in range(len(fronts)) if fronts[i] == backs[i]}\n",
    "        \n",
    "        ret = 2001\n",
    "        for n in fronts:\n",
    "            if n in same:\n",
    "                continue\n",
    "            ret = min(ret, n)\n",
    "        for n in backs:\n",
    "            if n in same:\n",
    "                continue\n",
    "            ret = min(ret, n)\n",
    "        return 0 if ret == 2001 else ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        ans = inf\n",
    "        data_len = len(fronts)\n",
    "        abandon_set = set()\n",
    "        for i in range(data_len):\n",
    "            if fronts[i] == backs[i]:\n",
    "                abandon_set.add(fronts[i])\n",
    "        for i in range(data_len):\n",
    "            f_in =  fronts[i]  in abandon_set\n",
    "            b_in = backs[i]  in abandon_set\n",
    "            if not ( f_in and b_in) :\n",
    "                if f_in:\n",
    "                    ans = min(backs[i], ans)\n",
    "                elif b_in:\n",
    "                    ans = min(fronts[i], ans)\n",
    "                else:\n",
    "                    ans = min(fronts[i], backs[i], ans)\n",
    "        return 0 if ans is inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        n=len(fronts)\n",
    "        ok=[0]*2001\n",
    "        for a,b in zip(fronts,backs):\n",
    "            if a==b:\n",
    "                ok[a]=2\n",
    "            else:\n",
    "                if ok[a]==0:\n",
    "                    ok[a]=1\n",
    "                if ok[b]==0:\n",
    "                    ok[b]=1\n",
    "        for i,o in enumerate(ok):\n",
    "            if o==1:\n",
    "                return i\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "       \n",
    "        notpos=set()\n",
    "        for i in range(len(fronts)):\n",
    "            if fronts[i]==backs[i]:\n",
    "                notpos.add(fronts[i])\n",
    "        all=list(set(fronts+backs))\n",
    "        all.sort()\n",
    "        for item in all:\n",
    "            if item not in notpos:\n",
    "                return item\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        len_list = len(fronts)\n",
    "        sumList = fronts + backs\n",
    "        # check num from the smallest number\n",
    "        num = 0\n",
    "        while True:\n",
    "            num += 1\n",
    "            if not num in sumList:\n",
    "                # check if we can end the range\n",
    "                ok = True\n",
    "                for val in sumList:\n",
    "                    if num < val:\n",
    "                        ok = False\n",
    "                        break\n",
    "                if ok:\n",
    "                    break\n",
    "                # continue if num not in list\n",
    "                continue\n",
    "            # check if num is correct\n",
    "            correctNum = True\n",
    "            for cnt in range(len_list):\n",
    "                if fronts[cnt] == backs[cnt] == num:\n",
    "                    correctNum = False\n",
    "                    break\n",
    "            if correctNum:\n",
    "                return num\n",
    "                    \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int: \n",
    "        dic = {}\n",
    "        m = inf\n",
    "        for i in range(len(fronts)):\n",
    "            if fronts[i] == backs[i]:\n",
    "                dic[fronts[i]] = True\n",
    "        for i in range(len(fronts)):\n",
    "            if fronts[i] not in dic:\n",
    "                m = min(m, fronts[i])\n",
    "            if backs[i] not in dic:\n",
    "                m = min(m, backs[i])\n",
    "        return m if m<=2000 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        length = len(fronts)\n",
    "        result = 2001\n",
    "        for i in range(length):\n",
    "            if fronts[i] == backs[i]:\n",
    "                continue\n",
    "            flag = True\n",
    "            for j in range(length):\n",
    "                if fronts[j] == fronts[i] and backs[j] == fronts[i]:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                result = result if result<=fronts[i] else fronts[i]\n",
    "            flag = True\n",
    "            for j in range(length):\n",
    "                if fronts[j] == backs[i] and backs[j] == backs[i]:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                result = result if result<=backs[i] else backs[i]\n",
    "        return result if result != 2001 else 0\n",
    "\n",
    "                \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        n = len(fronts)\n",
    "        same = set()\n",
    "        for i in range(n):\n",
    "            if fronts[i] == backs[i]:\n",
    "                same.add(fronts[i])\n",
    "        res = 3000\n",
    "        for a in fronts:\n",
    "            if a < res and a not in same:\n",
    "                res = a\n",
    "        for a in backs:\n",
    "            if a < res and a not in same:\n",
    "                res = a\n",
    "        return res if res < 3000 else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        forbidden = {x for x, y in zip(fronts, backs) if x == y}\n",
    "        return min((x for x in fronts + backs if x not in forbidden), default=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        has=[]\n",
    "        res=0\n",
    "        for i in range(len(fronts)):\n",
    "            if fronts[i]==backs[i]:\n",
    "                has.append(fronts[i])\n",
    "        \n",
    "        for i in range(len(fronts)):\n",
    "            if fronts[i] not in has:\n",
    "                res = min(res,fronts[i]) if res!=0 else fronts[i]\n",
    "            if backs[i] not in has:\n",
    "                res = min(res,backs[i]) if res!=0 else backs[i]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        n = len(fronts)\n",
    "        same = set()\n",
    "        for i in range(n):\n",
    "            if fronts[i] == backs[i]:\n",
    "                same.add(fronts[i])\n",
    "        res = 3000\n",
    "        for a in fronts:\n",
    "            if a < res and a not in same:\n",
    "                res = a\n",
    "        for a in backs:\n",
    "            if a < res and a not in same:\n",
    "                res = a\n",
    "        return res if res < 3000 else 0\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        #最小的只出现一次的数\n",
    "        mp = {}\n",
    "        for i in range(len(fronts)):\n",
    "            if fronts[i] == backs[i]:\n",
    "                mp[fronts[i]]=1\n",
    "        res = 3000\n",
    "        for i in fronts:\n",
    "            if i not in mp and i < res:\n",
    "                res = i\n",
    "        for i in backs:\n",
    "            if i not in mp and i < res:\n",
    "                res = i\n",
    "        return res if res < 3000 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        ans = 2000\n",
    "        n = len(fronts)\n",
    "        temp = 0 # 临时存放卡片正面的数字\n",
    "        \n",
    "        for i in range(n):\n",
    "            # 翻转[1,n)张\n",
    "            if fronts[i] != backs[i]:\n",
    "\n",
    "                temp = fronts[i]\n",
    "                if temp not in fronts:\n",
    "                    ans = min(ans, temp)\n",
    "\n",
    "                fronts[i] = backs[i]\n",
    "                if temp not in fronts:\n",
    "                    ans = min(ans, temp)\n",
    "                fronts[i] = temp\n",
    "\n",
    "                temp = backs[i]\n",
    "                backs[i] = 20001\n",
    "\n",
    "                if temp not in backs:\n",
    "                    ans = min(ans, temp)\n",
    "\n",
    "            # 一张都不翻转\n",
    "            if backs[i] not in fronts:\n",
    "                ans = min(ans, backs[i])\n",
    "\n",
    "            # 翻转n张\n",
    "            if fronts[i] not in backs:\n",
    "                ans = min(ans, fronts[i])\n",
    "          \n",
    "        if ans == 2000:\n",
    "            ans = 0\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        n = len(fronts)\n",
    "        res = inf\n",
    "        forbid = {fronts[i] for i in range(n) if fronts[i] == backs[i]}\n",
    "\n",
    "        for num in chain(fronts, backs):\n",
    "            if num not in forbid:\n",
    "                res = min(res, num)\n",
    "        return res if res != inf else 0\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        forbidden = {x for x, y in zip(fronts, backs) if x == y}\n",
    "        return min((x for x in fronts + backs if x not in forbidden), default=0)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        set_duplicate = {front for front, back in zip(fronts, backs) if front == back}\n",
    "        return min((num for num in fronts + backs if num not in set_duplicate), default=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        n = len(fronts)\n",
    "        same = set()\n",
    "        for i in range(n):\n",
    "            if fronts[i] == backs[i]:\n",
    "                same.add(fronts[i])\n",
    "        res = 3000\n",
    "        for a in fronts:\n",
    "            if a < res and a not in same:\n",
    "                res = a\n",
    "        for a in backs:\n",
    "            if a < res and a not in same:\n",
    "                res = a\n",
    "        return res if res < 3000 else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        nums = [0] * 2001\n",
    "        for i in range(len(fronts)):\n",
    "            if fronts[i] == backs[i]: nums[fronts[i]] = -1\n",
    "            if nums[fronts[i]] == 0:  nums[fronts[i]] =  1\n",
    "            if nums[ backs[i]] == 0:  nums[ backs[i]] =  1\n",
    "        for i in range(2001):\n",
    "            if nums[i] == 1: return i\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        same = []\n",
    "        res = []\n",
    "        for i in range(len(fronts)):\n",
    "            if fronts[i] == backs[i]:\n",
    "                same.append(fronts[i])\n",
    "        for x in fronts + backs:\n",
    "            if x not in same:\n",
    "                res.append(x)\n",
    "        return min(res) if res else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        forbidden = {x for x, y in zip(fronts, backs) if x == y}\n",
    "        return min((x for x in fronts + backs if x not in forbidden), default=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "      if len(fronts) == 1:\n",
    "        return 0 if fronts[0] == backs[0] else min(fronts[0], backs[0])\n",
    "      res = 3000\n",
    "      exce = set()\n",
    "      for i in range(len(fronts)):\n",
    "        if fronts[i] == backs[i]:\n",
    "          exce.add(fronts[i])\n",
    "      for i in range(len(fronts)):\n",
    "        if fronts[i] != backs[i]:\n",
    "          if fronts[i] in exce:\n",
    "            MIN = min(res, backs[i])\n",
    "          elif backs[i] in exce:\n",
    "            MIN = min(res, fronts[i])\n",
    "          else:\n",
    "            MIN = min(res, backs[i], fronts[i])\n",
    "          if MIN not in exce:\n",
    "            res = MIN\n",
    "      return res if res != 3000 else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        ans, n = float('inf'), len(fronts)\n",
    "        for i in range(n):\n",
    "            flag_1 = flag_2 = 0\n",
    "            for j in range(n):\n",
    "                cond_1 = backs[j] == fronts[i] and fronts[j] == fronts[i]\n",
    "                cond_2 = backs[j] == backs[i] and fronts[j] == backs[i]\n",
    "                if (cond_1 and cond_2) or (flag_1 and flag_2):\n",
    "                    flag_1 = flag_2 = 1\n",
    "                    break\n",
    "                elif cond_1:\n",
    "                    flag_1 = 1\n",
    "                elif cond_2:\n",
    "                    flag_2 = 1\n",
    "            if flag_1 == 0 and flag_2 == 0:\n",
    "                ans = min(ans, fronts[i], backs[i])\n",
    "            elif flag_1 == 0:\n",
    "                ans = min(ans, fronts[i])\n",
    "            elif flag_2 == 0:\n",
    "                ans = min(ans, backs[i]) \n",
    "        return 0 if ans == float('inf') else ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        forbidden = {x for x, y in zip(fronts, backs) if x == y}\n",
    "        return min((x for x in fronts + backs if x not in forbidden), default=0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        s = set()\n",
    "\n",
    "        for i, v in enumerate(fronts):\n",
    "            if v == backs[i]:\n",
    "                s.add(v)\n",
    "                \n",
    "\n",
    "        ans = float(\"inf\")\n",
    "\n",
    "        for i, v in enumerate(fronts):\n",
    "            if v not in s:\n",
    "                ans = min(ans, v)\n",
    "                \n",
    "            if backs[i] not in s:\n",
    "                ans = min(ans, backs[i])\n",
    "                \n",
    "        \n",
    "        return 0 if ans == float(\"inf\") else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        same = set()\n",
    "        for i in range(len(fronts)):\n",
    "            if fronts[i] == backs[i]:\n",
    "                same.add(fronts[i])\n",
    "        \n",
    "        min_num = float('inf')\n",
    "        for num in fronts + backs:\n",
    "            if num not in same:\n",
    "                min_num = min(min_num, num)\n",
    "        \n",
    "        return min_num if min_num != float('inf') else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        return min(set(fronts+backs)-{i for i, j in zip(fronts, backs) if i == j} or [0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        n = len(fronts)\n",
    "        same = set()\n",
    "        for i in range(n):\n",
    "            if fronts[i] == backs[i]:\n",
    "                same.add(fronts[i])\n",
    "        \n",
    "        res = 3000 \n",
    "        for a in fronts:\n",
    "            if a < res and a not in same:\n",
    "                res = a \n",
    "        for a in backs:\n",
    "            if a < res and a not in same:\n",
    "                res = a \n",
    "        \n",
    "        return res if res < 3000 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        n = len(fronts)\n",
    "        iset = set()\n",
    "        nset = set()\n",
    "        for i in range(n):\n",
    "            if fronts[i] == backs[i]:\n",
    "                iset.add(i)\n",
    "                nset.add(fronts[i])\n",
    "        \n",
    "        res = float('inf')\n",
    "        for i in range(n):\n",
    "            if i in iset:\n",
    "                continue\n",
    "            if fronts[i] not in nset:\n",
    "                res = min(res, fronts[i])\n",
    "            if backs[i] not in nset:\n",
    "                res = min(res, backs[i])\n",
    "        if res == float(inf):\n",
    "            return 0\n",
    "        else:\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        forbidden = {x for x, y in zip(fronts, backs) if x == y}\n",
    "        return min((x for x in fronts + backs if x not in forbidden), default=0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        same = set()\n",
    "        for i in range(len(fronts)):\n",
    "            if fronts[i] == backs[i]:\n",
    "                same.add(fronts[i])\n",
    "        res = 2001\n",
    "        for front in fronts:\n",
    "            if front < res and front not in same:\n",
    "                res = front\n",
    "        for back in backs:\n",
    "            if back < res and back not in same:\n",
    "                res = back\n",
    "        return res if res < 2001 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        ans=inf\n",
    "        s=set()\n",
    "        for i in range(len(fronts)):\n",
    "            if fronts[i]==backs[i]:s.add(fronts[i])\n",
    "        for i in range(len(fronts)):\n",
    "            if fronts[i] not in s:\n",
    "                ans=min(ans,fronts[i])\n",
    "            if backs[i] not in s:\n",
    "                ans=min(ans,backs[i])\n",
    "        return 0 if ans==inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        n = len(fronts)\n",
    "        temp = set()\n",
    "        for i in range(n):\n",
    "            if fronts[i] == backs[i]:\n",
    "                temp.add(fronts[i])\n",
    "        res = 5000\n",
    "        for i in range(n):\n",
    "            if res > fronts[i] and fronts[i] not in temp:\n",
    "                res = fronts[i]\n",
    "            if res > backs[i] and backs[i] not in temp:\n",
    "                res = backs[i]\n",
    "        return res if res < 5000 else 0\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "      same=set()\n",
    "      ans=float('inf')\n",
    "      n=len(fronts)\n",
    "      for i in range(n):\n",
    "        if fronts[i]==backs[i]:\n",
    "          same.add(fronts[i])\n",
    "      for i in range(n):\n",
    "        if fronts[i]<ans and fronts[i] not in same:\n",
    "          ans=fronts[i]\n",
    "      for i in range(n):\n",
    "        if backs[i]<ans and backs[i] not in same:\n",
    "          ans=backs[i]\n",
    "      return ans if ans<3000 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        s = {f for f, b in zip(fronts, backs) if f == b}\n",
    "\n",
    "        return min((c for c in chain(fronts, backs) if c not in s), default=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        # Greedy\n",
    "        not_possible = set()\n",
    "        n = len(fronts)\n",
    "        for i in range(n):\n",
    "            if backs[i] == fronts[i]:\n",
    "                not_possible.add(backs[i])\n",
    "        all = sorted(set(fronts + backs))\n",
    "        for x in all:\n",
    "            if x not in not_possible:\n",
    "                return x\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        forbidden = {x for x, y in zip(fronts, backs) if x == y}\n",
    "        return min((x for x in fronts + backs if x not in forbidden), default=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter, defaultdict\n",
    "from heapq import heappush, heappop\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        n = len(fronts)\n",
    "        visited = set()\n",
    "        h = []\n",
    "        s = set()\n",
    "        for i in range(n):\n",
    "            f = fronts[i]\n",
    "            b = backs[i]\n",
    "\n",
    "            if f == b:\n",
    "                visited.add(f)\n",
    "                s.add(f)\n",
    "            else:\n",
    "                if f not in visited:\n",
    "                    heappush(h, f)\n",
    "                    visited.add(f)\n",
    "                if b not in visited:\n",
    "                    heappush(h, b)\n",
    "                    visited.add(b)\n",
    "\n",
    "        while h:\n",
    "            v = heappop(h)\n",
    "            if v in s:\n",
    "                continue\n",
    "            return v\n",
    "\n",
    "        return 0\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    pass\n",
    "    # assert 2 == Solution().flipgame([1, 2, 4, 4, 7], [1, 3, 4, 1, 3])\n",
    "    # assert 0 == Solution().flipgame([1], [1])\n",
    "    # assert 2 == Solution().flipgame([1, 1], [2, 1])\n",
    "    # assert 1 == Solution().flipgame([1, 1], [2, 2])\n",
    "    # assert 1 == Solution().flipgame([2, 2], [1, 1])\n",
    "    # assert 2 == Solution().flipgame([2, 2, 5, 1, 2], [4, 1, 2, 1, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        same = set()\n",
    "        for i in range(len(fronts)):\n",
    "            if fronts[i] == backs[i]:\n",
    "                same.add(fronts[i])\n",
    "\n",
    "        res = 2001\n",
    "        for i in range(len(fronts)):\n",
    "            if fronts[i] not in same:\n",
    "                res = min(res, fronts[i])\n",
    "            if backs[i] not in same:\n",
    "                res = min(res, backs[i])\n",
    "        return res if res != 2001 else 0\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        # for i in range(len(fronts)):\n",
    "        #     if fronts[i] == backs[i]:\n",
    "        #         continue\n",
    "        #     Flag = True\n",
    "        #     # 先选择正面的数字\n",
    "        #     for j in range(len(fronts)):\n",
    "        #         if i == j:\n",
    "        #             continue \n",
    "        #         if fronts[j] == fronts[i] and backs[j] == fronts[i]:\n",
    "        #             Flag = False\n",
    "        #             break\n",
    "        #     if Flag:\n",
    "        #         return fronts[i]\n",
    "        #     Flag = True\n",
    "        #     for j in range(len(fronts)):\n",
    "        #         if i == j:\n",
    "        #             continue \n",
    "        #         if fronts[j] == backs[i] and backs[j] == backs[i]:\n",
    "        #             Flag = False\n",
    "        #             break\n",
    "        #     if Flag:\n",
    "        #         return backs[i]\n",
    "        # return 0\n",
    "\n",
    "        # hashset = set(fronts+backs)\n",
    "        # lis = list(hashset) \n",
    "        # lis.sort()\n",
    "        # for i in lis:\n",
    "        #     Flag = True\n",
    "        #     for j in range(len(fronts)):\n",
    "        #         if fronts[j] == i and backs[j] == i:\n",
    "        #             Flag = False\n",
    "        #             break\n",
    "        #     if Flag:\n",
    "        #         return i\n",
    "        # return 0\n",
    "\n",
    "        buxing = set()\n",
    "        for j in range(len(fronts)):\n",
    "            if fronts[j] == backs[j]:\n",
    "                buxing.add(fronts[j])\n",
    "        res = inf\n",
    "        for i in range(len(fronts)):\n",
    "            if fronts[i] not in buxing:\n",
    "                res = min(res,fronts[i])\n",
    "            if backs[i] not in buxing:\n",
    "                res = min(res,backs[i]) \n",
    "        if res > 10000:\n",
    "            return 0\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\r\n",
    "class Solution:\r\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\r\n",
    "        invalid=set()\r\n",
    "        ret=[]\r\n",
    "        for i in range(len(fronts)):\r\n",
    "            if backs[i]==fronts[i]:\r\n",
    "                invalid.add(backs[i])\r\n",
    "            while ret and ret[0] in invalid:\r\n",
    "                heapq.heappop(ret)\r\n",
    "            if backs[i] not in invalid:\r\n",
    "                heapq.heappush(ret,backs[i])\r\n",
    "            if fronts[i] not in invalid:\r\n",
    "                heapq.heappush(ret,fronts[i])\r\n",
    "        return ret[0] if ret else 0\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        \n",
    "        # fronts = [i+1 for i in range(1000)]\n",
    "        # fronts = [1000-i for i in range(1000)]\n",
    "        number_list = sorted(set(fronts+backs))\n",
    "        for cur_min in number_list:\n",
    "            for cur_front, cur_back in zip(fronts,backs):\n",
    "                if cur_front==cur_min:\n",
    "                    if cur_back==cur_min:\n",
    "                        break\n",
    "            else:\n",
    "                return cur_min\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "\n",
    "        n = len(fronts)\n",
    "        dbl_sided = set()\n",
    "        for i in range(n):\n",
    "            if fronts[i] == backs[i]:\n",
    "                dbl_sided.add(fronts[i])\n",
    "        ans = 2001\n",
    "        for i in range(n):\n",
    "            if fronts[i] in dbl_sided and backs[i] in dbl_sided:\n",
    "                continue\n",
    "            elif fronts[i] in dbl_sided:\n",
    "                ans = min(backs[i], ans)\n",
    "            elif backs[i] in dbl_sided:\n",
    "                ans = min(fronts[i], ans)\n",
    "            else:\n",
    "                ans = min(min(fronts[i], backs[i]), ans)\n",
    "        \n",
    "        if ans == 2001:\n",
    "            return 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        same = set()\n",
    "        for i in range(len(fronts)):\n",
    "            if fronts[i] == backs[i]:\n",
    "                same.add(fronts[i])\n",
    "        all = list(set(fronts + backs))\n",
    "        # print(fronts, backs, all.sort())\n",
    "        for num in sorted(all):\n",
    "            if num not in same:\n",
    "                return num\n",
    "        return 0\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        fronts.extend(backs)\n",
    "        a=list(set(fronts))\n",
    "        b=[]\n",
    "        for i in range(len(backs)):\n",
    "            if fronts[i]==backs[i]:\n",
    "                b.append(fronts[i])\n",
    "        c=[]\n",
    "        for i in a:\n",
    "            if i not in b:\n",
    "                c.append(i)\n",
    "        if c==[]:\n",
    "            return 0\n",
    "        return min(c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        k = set()\n",
    "        res = 0\n",
    "        for i in range(len(fronts)):\n",
    "            if fronts[i] == backs[i]:\n",
    "                k.add(fronts[i])\n",
    "        for i in range(len(fronts)):\n",
    "            f = fronts[i]\n",
    "            b = backs[i]\n",
    "            if f == b or (f in k and b in k):\n",
    "                continue\n",
    "            if f in k:\n",
    "                num = b\n",
    "            elif b in k:\n",
    "                num = f\n",
    "            else:\n",
    "                num = min(f, b)\n",
    "            res = min(res, num) if res != 0 else num\n",
    "        return  res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        flag = set(fronts[i] for i in range(len(fronts)) if fronts[i]==backs[i])\n",
    "        return min(((set(fronts) | set(backs)) - flag) | {1001}) % 1001"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\r\n",
    "        invalid = set()\r\n",
    "        ret = 3000\r\n",
    "        for i in range(len(fronts)):\r\n",
    "            if backs[i] == fronts[i]:\r\n",
    "                invalid.add(backs[i])\r\n",
    "        for f in fronts:\r\n",
    "            if f not in invalid:\r\n",
    "                ret = min(ret, f)\r\n",
    "        for b in backs:\r\n",
    "            if b not in invalid:\r\n",
    "                ret = min(ret, b)\r\n",
    "        return ret % 3000\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        forbidden = {x for x, y in zip(fronts, backs) if x == y}\n",
    "        return min((x for x in fronts + backs if x not in forbidden), default=0)\n",
    "\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        def flip(idx):\n",
    "            fronts[idx], backs[idx] = backs[idx], fronts[idx]\n",
    "\n",
    "        n = len(fronts)\n",
    "        res = float('inf')\n",
    "        for i in range(n):\n",
    "            if fronts[i] == backs[i]:\n",
    "                continue\n",
    "            num1, num2 = backs[i], fronts[i]\n",
    "            for j in range(n):\n",
    "                if fronts[j] == num1:\n",
    "                    flip(j)\n",
    "            if num1 not in fronts:\n",
    "                res = min(res, num1)\n",
    "\n",
    "            for j in range(n):\n",
    "                if fronts[j] == num2:\n",
    "                    flip(j)\n",
    "            if num2 not in fronts:\n",
    "                res = min(res, num2)\n",
    "            # print(fronts, backs)\n",
    "\n",
    "        return res if res != float('inf') else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        return min(((set(fronts) | set(backs)) - set(fronts[i] for i in range(len(fronts)) if fronts[i]==backs[i])) | {1001}) % 1001"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        avail_num = set()\n",
    "        non_avail = set()\n",
    "        for i in range(len(fronts)):\n",
    "            if fronts[i] == backs[i]:\n",
    "                non_avail.add( fronts[i] )\n",
    "                avail_num.discard( fronts[i] )\n",
    "            else:\n",
    "                if fronts[i] not in non_avail:\n",
    "                    avail_num.add(fronts[i])\n",
    "                if backs[i] not in non_avail:\n",
    "                    avail_num.add(backs[i])\n",
    "        if avail_num:\n",
    "            return min(avail_num)\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        same = set()\n",
    "        for i in range(len(fronts)):\n",
    "            if fronts[i] == backs[i]:\n",
    "                same.add(fronts[i])\n",
    "\n",
    "        res = 2001\n",
    "        for i in range(len(fronts)):\n",
    "            if fronts[i] not in same:\n",
    "                res = min(res, fronts[i])\n",
    "            if backs[i] not in same:\n",
    "                res = min(res, backs[i])\n",
    "        return res if res != 2001 else 0\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "\n",
    "        # 找出正面和反面不同的数\n",
    "\n",
    "        rs = set(fronts)\n",
    "        rs.update(set(backs))\n",
    "        for front, back in zip(fronts, backs):\n",
    "            if front == back:\n",
    "                rs.discard(front)\n",
    "        return min(rs) if rs else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        m = len(fronts)\n",
    "        same = []\n",
    "        for i in range(m):\n",
    "            if fronts[i] == backs[i]:\n",
    "                same.append(fronts[i])\n",
    "        record = []\n",
    "        for i in range(m):\n",
    "            if fronts[i] not in same:\n",
    "                record.append(fronts[i])\n",
    "            if backs[i] not in same:\n",
    "                record.append(backs[i])\n",
    "        return min(record) if record else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter, defaultdict\n",
    "from heapq import heappush, heappop\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        n = len(fronts)\n",
    "        visited = set()\n",
    "        h = []\n",
    "        s = set()\n",
    "        for i in range(n):\n",
    "            f = fronts[i]\n",
    "            b = backs[i]\n",
    "            if f not in visited:\n",
    "                heappush(h, f)\n",
    "                visited.add(f)\n",
    "            if b not in visited:\n",
    "                heappush(h, b)\n",
    "                visited.add(b)\n",
    "\n",
    "            if f == b:\n",
    "                s.add(f)\n",
    "\n",
    "        while h:\n",
    "            v = heappop(h)\n",
    "            if v in s:\n",
    "                continue\n",
    "            return v\n",
    "\n",
    "        return 0\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    pass\n",
    "    # assert 2 == Solution().flipgame([1, 2, 4, 4, 7], [1, 3, 4, 1, 3])\n",
    "    # assert 0 == Solution().flipgame([1], [1])\n",
    "    # assert 2 == Solution().flipgame([1, 1], [2, 1])\n",
    "    # assert 1 == Solution().flipgame([1, 1], [2, 2])\n",
    "    # assert 1 == Solution().flipgame([2, 2], [1, 1])\n",
    "    # assert 2 == Solution().flipgame([2, 2, 5, 1, 2], [4, 1, 2, 1, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(fronts)\n",
    "        table = set()\n",
    "        cnt = set()\n",
    "        for i in range(n):\n",
    "            if fronts[i]==backs[i]:\n",
    "                cnt |= {fronts[i]}\n",
    "            else:\n",
    "                table |= {fronts[i]}\n",
    "                table |= {backs[i]}\n",
    "        return min(table-cnt) if (table-cnt) else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        forbidden = {x for x,y in zip(fronts, backs) if x == y}\n",
    "        return min((x for x in fronts + backs if x not in forbidden), default = 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        n = len(fronts)\n",
    "        alist = []\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if fronts[i]==backs[i]:\n",
    "                alist.append(fronts[i])\n",
    " \n",
    "        for i in fronts:\n",
    "            if i not in alist:\n",
    "                ans.append(i)\n",
    "        for i in backs:\n",
    "            if i not in alist:\n",
    "                ans.append(i)\n",
    "        if len(ans)!=0:\n",
    "            return min(ans)\n",
    "        else:\n",
    "            return 0\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        same = set()\n",
    "        for i in range(len(fronts)):\n",
    "            if fronts[i] == backs[i]:\n",
    "                same.add(fronts[i])\n",
    "        all = list(set(fronts) | set(backs))\n",
    "        # print(fronts, backs, all.sort())\n",
    "        for num in sorted(all):\n",
    "            if num not in same:\n",
    "                return num\n",
    "        return 0\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        dic=defaultdict(lambda:True)\n",
    "        for a,b in zip(fronts,backs):\n",
    "            if a==b:\n",
    "                dic[a]=False\n",
    "        for a in sorted(fronts+backs):\n",
    "            if dic[a]:\n",
    "                return a\n",
    "        return 0\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        # Greedy\n",
    "        not_possible = set()\n",
    "        n = len(fronts)\n",
    "        for i in range(n):\n",
    "            if backs[i] == fronts[i]:\n",
    "                not_possible.add(backs[i])\n",
    "        all = sorted(set(fronts + backs))\n",
    "        for x in all:\n",
    "            if x not in not_possible:\n",
    "                return x\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        both = set()\n",
    "        res = set()\n",
    "        for x, y in zip(fronts, backs):\n",
    "            if x == y:\n",
    "                both.add(x)\n",
    "            else:\n",
    "                res.add(x)\n",
    "                res.add(y)\n",
    "        \n",
    "        res = res.difference(both)\n",
    "        return min(res) if res else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        forbidden = {x for x,y in zip(fronts,backs) if x==y}\n",
    "        return min((x for x in fronts + backs if x not in forbidden),default = 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        s = set(fronts + backs)\n",
    "        n = len(fronts)\n",
    "        for i in range(n):\n",
    "            if fronts[i] == backs[i] and fronts[i] in s:\n",
    "                s.remove(fronts[i])\n",
    "\n",
    "        if len(s) == 0:\n",
    "            return 0\n",
    "        return min(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        seen = set()\n",
    "        n = len(fronts)\n",
    "        for i in range(n):\n",
    "            if fronts[i] == backs[i]:\n",
    "                seen.add(fronts[i])\n",
    "        \n",
    "        res = float(\"inf\")\n",
    "        for card in fronts:\n",
    "            if card not in seen and card < res: res = card\n",
    "        for card in backs:\n",
    "            if card not in seen and card < res: res = card\n",
    "        \n",
    "        return res if res != float(\"inf\") else 0\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # n = len(fronts)\n",
    "        # same = set()\n",
    "        # for i in range(n):\n",
    "        #     if fronts[i] == backs[i]:\n",
    "        #         same.add(fronts[i])\n",
    "        \n",
    "        # res = 3000\n",
    "\n",
    "        # for a in fronts:\n",
    "        #     if a < res and a not in same:\n",
    "        #         res = a\n",
    "        \n",
    "        # for a in backs:\n",
    "        #     if a < res and a not in same:\n",
    "        #         res = a\n",
    "        \n",
    "        # return res if res < 3000 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        res = 3000\n",
    "        flg = [True] * 2001\n",
    "        for front, back in zip(fronts, backs):\n",
    "            if front == back:\n",
    "                flg[front] = False\n",
    "        for front, back in zip(fronts, backs):\n",
    "            if flg[front] and front < res:\n",
    "                res = front\n",
    "            if flg[back] and back < res:\n",
    "                res = back\n",
    "        if res == 3000:\n",
    "            return 0\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        both = set()\n",
    "        res = set()\n",
    "        for x, y in zip(fronts, backs):\n",
    "            if x == y:\n",
    "                both.add(x)\n",
    "            else:\n",
    "                res.add(x)\n",
    "                res.add(y)\n",
    "        \n",
    "        res = res.difference(both)\n",
    "        return min(res) if res else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        n = len(fronts)\n",
    "        ans = set(fronts) | set(backs)\n",
    "        for i in range(n):\n",
    "            if fronts[i] == backs[i]:\n",
    "                if fronts[i] in ans:\n",
    "                    ans.remove(fronts[i])\n",
    "            # print(ans)\n",
    "        return min(ans) if ans else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        n = len(fronts)\n",
    "        same = set()\n",
    "        for i in range(n):\n",
    "            if fronts[i] == backs[i]:\n",
    "                same.add(fronts[i])\n",
    "        res = 3000\n",
    "        for a in fronts:\n",
    "            if a < res and a not in same:\n",
    "                res = a\n",
    "        for a in backs:\n",
    "            if a < res and a not in same:\n",
    "                res = a\n",
    "        return res if res < 3000 else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        n = len(fronts)\n",
    "        s = set()\n",
    "        ret = 10000\n",
    "        for i in range(n):\n",
    "            if fronts[i] == backs[i]:\n",
    "                s.add(fronts[i])\n",
    "\n",
    "        for i in range(n):\n",
    "            if fronts[i] == backs[i]:\n",
    "                continue\n",
    "            else:\n",
    "                if fronts[i] not in s:\n",
    "                    ret = min(ret, fronts[i])\n",
    "                if backs[i] not in s:\n",
    "                    ret = min(ret, backs[i])\n",
    "        return 0 if ret == 10000 else ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        forbidden = {x for x, y in zip(fronts, backs) if x == y}\n",
    "        return min((x for x in fronts + backs if x not in forbidden), default=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        set1 = set()\n",
    "        set2 = set()\n",
    "        for i in range(len(fronts)):\n",
    "            f = fronts[i]\n",
    "            b = backs[i]\n",
    "            if f == b:\n",
    "                set1.add(f)\n",
    "            else:\n",
    "                set2.add(f)\n",
    "                set2.add(b)\n",
    "        set3 = set2 - set1\n",
    "        return min(set3) if set3 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipgame(self, fronts: List[int], backs: List[int]) -> int:\n",
    "        strict = set()\n",
    "        choice = set()\n",
    "        for i,j in zip(fronts,backs):\n",
    "            if i==j:\n",
    "                strict.add(i)\n",
    "            else:\n",
    "                choice.add(i)\n",
    "                choice.add(j)\n",
    "        return min(choice - strict, default = 0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
